import java.util.Scanner;

public class demo {

    // 字符串计数▲▲▲
//    求字典序在 s1 和 s2 之间的，长度在 len1 到 len2 的字符串的个数，结果 mod 1000007。
//    输入描述:
//每组数据包涵s1（长度小于50），s2（长度小于50），len1（小于50），len2（大于len1，小于50）
//    输入
//ab ce 1 2
//    输出
//56

    //    思路:根据题中给出的例子，这个字符串只包含小写字母，不然答案就不应该是56了
//    所以只包含小写字母的字符串可以看成26进制的数
//1.将s1和s2补位len2 因为len2>len1  可以把计算的数先保存在数组中 之后在  该数*26^n计算
//2.将s1和s2中对应位置的字符相减-->for取到每一位相减-->保存
//3.进行运算
//4.需要给最终的结果-1 % 1000007
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            // 因为如果长度大于字符串的个数 我们要进行拼接 再计算
            StringBuffer s1 = new StringBuffer(scanner.next());
            StringBuffer s2 = new StringBuffer(scanner.next());
            int len1 = scanner.nextInt();
            int len2 = scanner.nextInt();
            // 要寻找s1和s2之间的数 如果需要增加的话 我们要在s1后加最小的字符 在s2后加最大的字符 满足s2字符-s1字符=26
            while (s1.length() < len2) {
                s1.append('a');
            }
            while (s2.length() < len2) {
                s2.append('z'+1);//因为一共有26个字母 如果'z'-'a'=25 多减去了一个字符 所以我们要加上1
            }
            // 这样理解
            // a b c d e
            // 1 2 3 4 5

            // 20 ~ 31  len1=1   len2=2
            // 当len1=1时  (3-2)*10^0-1=0
            // 当len2=2时  (3-2)*10^1 + (1-0)*10^0  ==  11   结果还需要 -1

            // 保存各相对位置的差数
            int[] arr = new int[len2];
            for (int i=0; i<len2; i++) {
                arr[i] = s2.charAt(i) - s1.charAt(i);
            }

            // 计数
            int count = 0;
            for (int i=len1; i<=len2; i++) {
                for (int j=0; j<len1; j++) {
                    count += arr[j]*Math.pow(26, i-j-1);
                }
            }

            // 最后结果记得-1
            System.out.println((count-1)%1000007);
        }
    }



    // 最长公共子序列
//我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
//例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。
//现在给你两个任意字符串（不包含空格），请帮忙计算它们的最长公共子序列的长度
//      输入
//  abcfbc abfcab
//  programming contest
//  abcd mnp
//      输出
//  4
//  2
//  0
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String m = scanner.next();
            String n = scanner.next();
            int len1 = m.length();
            int len2 = n.length();
            int[][] arr = new int[len1+1][len2+1];
            for (int i=1; i<=len1; i++) {
                for (int j=1; j<=len2; j++) {
                    if (m.charAt(i-1) != n.charAt(j-1)) {
                        arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);
                    }else {
                        arr[i][j] = Math.max(arr[i][j], arr[i-1][j-1]+1);
                    }
                }
            }
            System.out.println(arr[len1][len2]);
        }
    }
}
